{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Finish the Race"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumFinishTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完成比赛的最少时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>tires</code>&nbsp;，其中&nbsp;<code>tires[i] = [f<sub>i</sub>, r<sub>i</sub>]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;种轮胎如果连续使用，第&nbsp;<code>x</code>&nbsp;圈需要耗时&nbsp;<code>f<sub>i</sub> * r<sub>i</sub><sup>(x-1)</sup></code>&nbsp;秒。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，如果&nbsp;<code>f<sub>i</sub> = 3</code>&nbsp;且&nbsp;<code>r<sub>i</sub> = 2</code>&nbsp;，且一直使用这种类型的同一条轮胎，那么该轮胎完成第&nbsp;<code>1</code>&nbsp;圈赛道耗时 <code>3</code>&nbsp;秒，完成第 <code>2</code>&nbsp;圈耗时&nbsp;<code>3 * 2 = 6</code>&nbsp;秒，完成第 <code>3</code>&nbsp;圈耗时&nbsp;<code>3 * 2<sup>2</sup> = 12</code>&nbsp;秒，依次类推。</li>\n",
    "</ul>\n",
    "\n",
    "<p>同时给你一个整数&nbsp;<code>changeTime</code>&nbsp;和一个整数&nbsp;<code>numLaps</code>&nbsp;。</p>\n",
    "\n",
    "<p>比赛总共包含&nbsp;<code>numLaps</code>&nbsp;圈，你可以选择 <strong>任意</strong>&nbsp;一种轮胎开始比赛。每一种轮胎都有 <strong>无数条</strong>&nbsp;。每一圈后，你可以选择耗费 <code>changeTime</code>&nbsp;秒 <strong>换成</strong>&nbsp;任意一种轮胎（也可以换成当前种类的新轮胎）。</p>\n",
    "\n",
    "<p>请你返回完成比赛需要耗费的 <strong>最少</strong>&nbsp;时间。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4\n",
    "<b>输出：</b>21\n",
    "<b>解释：</b>\n",
    "第 1 圈：使用轮胎 0 ，耗时 2 秒。\n",
    "第 2 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。\n",
    "第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。\n",
    "第 4 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。\n",
    "总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。\n",
    "完成比赛的最少时间为 21 秒。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5\n",
    "<b>输出：</b>25\n",
    "<b>解释：</b>\n",
    "第 1 圈：使用轮胎 1 ，耗时 2 秒。\n",
    "第 2 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。\n",
    "第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。\n",
    "第 4 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。\n",
    "第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。\n",
    "总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。\n",
    "完成比赛的最少时间为 25 秒。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= tires.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>tires[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= f<sub>i</sub>, changeTime &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>2 &lt;= r<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= numLaps &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-finish-the-race](https://leetcode.cn/problems/minimum-time-to-finish-the-race/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-finish-the-race](https://leetcode.cn/problems/minimum-time-to-finish-the-race/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,3],[3,4]]\\n5\\n4', '[[1,10],[2,2],[3,4]]\\n6\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        min_sec = [inf] * 18\n",
    "        for f, r in tires:\n",
    "            x, time, sum = 1, f, 0\n",
    "            while time <= changeTime + f:\n",
    "                sum += time\n",
    "                min_sec[x]= min(min_sec[x], sum)\n",
    "                time *= r\n",
    "                x += 1\n",
    "        \n",
    "        f = [0] * (numLaps + 1)\n",
    "        f[0] = -changeTime\n",
    "\n",
    "        for i in range(1, numLaps + 1):\n",
    "            f[i] = changeTime + min(f[i-j] + min_sec[j] for j in range(1, min(18, i + 1)))\n",
    "        \n",
    "        return f[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        min_sec = [inf] * 18\n",
    "\n",
    "        sort_tires = sorted({(f, r) for f, r in tires})\n",
    "        def unique_and_smaller_tires():\n",
    "            lo_r = inf\n",
    "            for f, r in sort_tires:\n",
    "                if r >= lo_r: continue\n",
    "                lo_r = r\n",
    "                yield (f, r)\n",
    "\n",
    "        for f, r in unique_and_smaller_tires():\n",
    "            x, time, sum = 1, f, 0\n",
    "            while time <= changeTime + f:\n",
    "                sum += time\n",
    "                min_sec[x]= min(min_sec[x], sum)\n",
    "                time *= r\n",
    "                x += 1\n",
    "        \n",
    "        f = [0] * (numLaps + 1)\n",
    "        f[0] = -changeTime\n",
    "\n",
    "        for i in range(1, numLaps + 1):\n",
    "            f[i] = changeTime + min(f[i-j] + min_sec[j] for j in range(1, min(18, i + 1)))\n",
    "        \n",
    "        return f[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        M = 2 * 10 ** 8\n",
    "        dp = [M] * (numLaps + 1)\n",
    "        mi = [M] * (numLaps + 1)\n",
    "        for f, r in tires:\n",
    "            mi[1] = min(mi[1], f)\n",
    "            now = tot = f\n",
    "            for i in range(2, numLaps + 1):\n",
    "                now *= r\n",
    "                tot += now\n",
    "                if tot >= M:\n",
    "                    break\n",
    "                mi[i] = min(mi[i], tot)\n",
    "            \n",
    "        dp[1] = mi[1]\n",
    "        for i in range(2, numLaps + 1):\n",
    "            dp[i] = mi[i]\n",
    "            for j in range(1, i):\n",
    "                if mi[j] == M:\n",
    "                    break\n",
    "                dp[i] = min(dp[i], dp[i - j] + mi[j] + changeTime)\n",
    "            # print(i, dp[i])\n",
    "        return dp[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        \n",
    "        # # 最初始的思路, 定义函数dfs(sur): 表示还剩sur圈时的最小耗时\n",
    "        # # 在设计记忆化搜索函数时, 参数数量应尽可能的少, 数据类型应尽可能的简单\n",
    "        # @cache\n",
    "        # def dfs(sur):\n",
    "        #     if sur == 0: return 0\n",
    "        #     ans = inf\n",
    "        #     # 枚举每个轮胎跑i圈的时间\n",
    "        #     for f, r in tires:\n",
    "        #         time = 0\n",
    "        #         for i in range(1, min(sur + 1, 18)):\n",
    "        #             t = f * r ** (i - 1)\n",
    "        #             if t > f + changeTime: break\n",
    "        #             time += t\n",
    "        #             ans = min(ans, changeTime + time + dfs(sur - i))\n",
    "        #     return ans\n",
    "        #     # 优化: 第一层枚举可以省略, 每次只需要贪心的选择连跑i圈用时最短的轮胎即可\n",
    "        # return dfs(numLaps) - changeTime\n",
    "        \n",
    "        # 省略枚举转为递推之后的代码\n",
    "        minTimeLis = [inf] * 18\n",
    "        for f, r in tires:\n",
    "            sum_, t = 0, f\n",
    "            for x in count(1):\n",
    "                sum_ += t\n",
    "                if t > f + changeTime: break\n",
    "                minTimeLis[x] = min(sum_, minTimeLis[x])\n",
    "                t *= r\n",
    "      \n",
    "        dp = [0] * (numLaps + 1)\n",
    "        \n",
    "        for i in range(1, numLaps + 1):\n",
    "            dp[i] = changeTime + min(dp[i - j] + minTimeLis[j] for j in range(1, min(18, i + 1)))\n",
    "        \n",
    "        return dp[numLaps] - changeTime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        minTimeLis = [inf] * 18\n",
    "        for f, r in tires:\n",
    "            sum_, t = 0, f\n",
    "            for x in count(1):\n",
    "                sum_ += t\n",
    "                if t > f + changeTime: break\n",
    "                minTimeLis[x] = min(sum_, minTimeLis[x])\n",
    "                t *= r\n",
    "      \n",
    "        dp = [0] * (numLaps + 1)\n",
    "        dp[0] = -changeTime\n",
    "\n",
    "        for i in range(1, numLaps + 1):\n",
    "            dp[i] = changeTime + min(dp[i - j] + minTimeLis[j] for j in range(1, min(18, i + 1)))\n",
    "        \n",
    "        return dp[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        minTimeLis = [inf] * 18\n",
    "        for f, r in tires:\n",
    "            sum_, t = 0, f\n",
    "            for x in count(1):\n",
    "                sum_ += t\n",
    "                if t > f + changeTime: break\n",
    "                minTimeLis[x] = min(sum_, minTimeLis[x])\n",
    "                t *= r\n",
    "      \n",
    "        dp = [0] * (numLaps + 1)\n",
    "        dp[0] = -changeTime\n",
    "\n",
    "        for i in range(1, numLaps + 1):\n",
    "            dp[i] = changeTime + min(dp[i - j] + minTimeLis[j] for j in range(1, min(18, i + 1)))\n",
    "        \n",
    "        return dp[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "\n",
    "        b = defaultdict(lambda:float('inf')) \n",
    "        def func(fi,ri):\n",
    "            x = 1 \n",
    "            r = 1\n",
    "            pre = fi * r \n",
    "            b[x] = min(b[x], pre) \n",
    "            while pre + fi * r * ri < (pre + changeTime + fi * ri):\n",
    "                x+=1\n",
    "                r *= ri \n",
    "                pre += fi * r \n",
    "                b[x] = min(b[x], pre) \n",
    "\n",
    "        for fi,ri in tires:\n",
    "            func(fi, ri) \n",
    "        arr = [(k, val) for k, val in b.items()]\n",
    "        #print(arr) \n",
    "        n = numLaps\n",
    "        dp = [float('inf')] * (n + 1) \n",
    "        dp[0] = -changeTime \n",
    "        for i in range(1, n+1):\n",
    "            for xi, ti in arr:\n",
    "                if i >= xi:\n",
    "                    dp[i] = min(dp[i], dp[i-xi] + ti + changeTime)\n",
    "        #print(dp)\n",
    "\n",
    "        return dp[n]\n",
    "\n",
    "\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "\n",
    "        f = defaultdict(lambda : float('inf')) \n",
    "        def func(fi, ri): \n",
    "            f[1] = min(f[1], fi)\n",
    "            tot = fi \n",
    "            b = fi\n",
    "            i = 2\n",
    "            while tot + b * ri <= tot + changeTime + fi:\n",
    "                f[i] = min(f[i], tot + b * ri) \n",
    "                tot += b * ri \n",
    "                b *= ri \n",
    "                i+=1 \n",
    "        for fi, ri in tires:\n",
    "            func(fi, ri) \n",
    "        dp = [float('inf')] * (numLaps+1)\n",
    "        dp[0] = 0 \n",
    "        for i in range(1, numLaps+1):\n",
    "            for x, cost in f.items():\n",
    "                if i > x:\n",
    "                    dp[i] = min(dp[i], dp[i-x] + cost + changeTime)\n",
    "                elif i == x:\n",
    "                    dp[i] = min(dp[i], cost)\n",
    "        return dp[numLaps]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        best=[float(\"inf\")]*18\n",
    "        maxdif=0\n",
    "        for f,r in tires:\n",
    "            onelap=f\n",
    "            cur=f\n",
    "            i=1\n",
    "            while onelap<changeTime+f:\n",
    "                onelap=onelap*r \n",
    "                best[i]=min(best[i],cur)\n",
    "                cur=cur+onelap\n",
    "                maxdif=max(i,maxdif)\n",
    "                i=i+1\n",
    "\n",
    "\n",
    "        dp=[float(\"inf\")]*(numLaps+1)\n",
    "        dp[0]=0\n",
    "        for i in range(1,numLaps+1):\n",
    "            for j in range(i,i-maxdif-1,-1):\n",
    "                dp[i]=min(dp[i],dp[j]+best[i-j]+changeTime)\n",
    "      # print(dp)\n",
    "        #print(best)\n",
    "        return dp[-1]-changeTime\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        minTimeLis = [inf] * 18\n",
    "        for f, r in tires:\n",
    "            sum_, t = 0, f\n",
    "            for x in count(1):\n",
    "                sum_ += t\n",
    "                if t > f + changeTime: break\n",
    "                minTimeLis[x] = min(sum_, minTimeLis[x])\n",
    "                t *= r\n",
    "      \n",
    "        dp = [0] * (numLaps + 1)\n",
    "        dp[0] = -changeTime\n",
    "\n",
    "        for i in range(1, numLaps + 1):\n",
    "            dp[i] = changeTime + min(dp[i - j] + minTimeLis[j] for j in range(1, min(18, i + 1)))\n",
    "        \n",
    "        return dp[numLaps]\n",
    "\n",
    "\n",
    "\n",
    "        min_sec = [inf] * 18\n",
    "        for f, r in tires:\n",
    "            x, time, sum = 1, f, 0\n",
    "            while time <= changeTime + f:\n",
    "                sum += time\n",
    "                min_sec[x] = min(min_sec[x], sum)\n",
    "                time *= r\n",
    "                x += 1\n",
    "        print(min_sec)\n",
    "        f = [0] * (numLaps + 1)\n",
    "        f[0] = -changeTime\n",
    "        for i in range(1, numLaps + 1):\n",
    "            f[i] = changeTime + min(f[i - j] + min_sec[j] for j in range(1, min(18, i + 1)))\n",
    "        return f[numLaps]\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/minimum-time-to-finish-the-race/solutions/1295939/jie-he-xing-zhi-qiao-miao-dp-by-endlessc-b963/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        M = min(f for f, r in tires) * numLaps + (numLaps - 1) * changeTime\n",
    "        dp = [M] * (numLaps + 1)\n",
    "        mi = [M] * (numLaps + 1)\n",
    "        for f, r in tires:\n",
    "            mi[1] = min(mi[1], f)\n",
    "            now = tot = f\n",
    "            for i in range(2, numLaps + 1):\n",
    "                now *= r\n",
    "                tot += now\n",
    "                if tot >= M:\n",
    "                    break\n",
    "                mi[i] = min(mi[i], tot)\n",
    "            \n",
    "        dp[1] = mi[1]\n",
    "        for i in range(2, numLaps + 1):\n",
    "            dp[i] = mi[i]\n",
    "            for j in range(1, i):\n",
    "                if mi[j] == M:\n",
    "                    break\n",
    "                dp[i] = min(dp[i], dp[i - j] + mi[j] + changeTime)\n",
    "        return dp[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        maxNum = min(numLaps + 1, 18)\n",
    "        same = [float('inf')] * maxNum\n",
    "        same[0] = 0\n",
    "        for f, r in tires:\n",
    "            cur = f \n",
    "            s = f\n",
    "            for i in range(1, maxNum):\n",
    "                same[i] = min(same[i], s) \n",
    "                cur *= r \n",
    "                s += cur \n",
    "        dp = [float('inf')] * (numLaps + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, numLaps + 1):\n",
    "            for j in range(1, maxNum):\n",
    "                dp[i] = min(dp[i], dp[i - j] + same[j] + changeTime * (i != j))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        N = len(tires)\n",
    "\n",
    "        min_nth = [inf]*18\n",
    "        for f,r in tires:\n",
    "            x,time ,sum = 1,f,0\n",
    "            while time<=changeTime+f:\n",
    "                sum += time\n",
    "                min_nth[x] = min(min_nth[x],sum)\n",
    "                time *= r\n",
    "                x += 1\n",
    "        \n",
    "        f = [0]*(numLaps+1)\n",
    "        f[0] = -changeTime\n",
    "        for i in range(1,numLaps+1):\n",
    "            f[i] = changeTime + min(f[i-j] + min_nth[j] for j in range(1,min(18,i+1)) ) \n",
    "        \n",
    "        return f[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        # mx = 1\n",
    "        # while pow(2, mx) <= changeTime:\n",
    "        #     mx += 1\n",
    "        mx = 17\n",
    "        min_v = [inf] * mx\n",
    "        for f, r in tires:\n",
    "            for j in range(1, mx):\n",
    "                if f * pow(r, j - 1) <= changeTime + f:\n",
    "                    tot = f * (pow(r, j) - 1) // (r - 1)\n",
    "                    min_v[j] = min(min_v[j], tot)\n",
    "                \n",
    "        f = [inf] * (numLaps + 1)\n",
    "        f[0] = -changeTime\n",
    "        for i in range(1, numLaps + 1):\n",
    "            for j in range(1, min(i + 1, mx)):\n",
    "                f[i] = min(f[i], f[i - j] + min_v[j] + changeTime)\n",
    "        \n",
    "        return f[-1]\n",
    "                    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        mx = 1\n",
    "        while pow(2, mx) <= 100000:\n",
    "            mx += 1\n",
    "\n",
    "        min_v = [inf] * mx\n",
    "        for f, r in tires:\n",
    "            for j in range(1, mx):\n",
    "                if f * pow(r, j - 1) <= changeTime + f:\n",
    "                    tot = f * (pow(r, j) - 1) // (r - 1)\n",
    "                    min_v[j] = min(min_v[j], tot)\n",
    "                \n",
    "        \n",
    "        # min_v = [inf] * mx\n",
    "        # for f, r in tires:\n",
    "        #     x, time, sum = 1, f, 0\n",
    "        #     while time <= changeTime + f:\n",
    "        #         sum += time\n",
    "        #         min_v[x] = min(min_v[x], sum)\n",
    "        #         time *= r\n",
    "        #         x += 1\n",
    "\n",
    "        \n",
    "        #print(f'{min_v}')\n",
    "        f = [inf] * (numLaps + 1)\n",
    "        f[0] = -changeTime\n",
    "        for i in range(1, numLaps + 1):\n",
    "            for j in range(1, min(i + 1, mx)):\n",
    "                f[i] = min(f[i], f[i - j] + min_v[j] + changeTime)\n",
    "        \n",
    "        return f[-1]\n",
    "                    \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        best=[float(\"inf\")]*18\n",
    "        best[0]=0\n",
    "        maxdiff=0\n",
    "        for f,r in tires:\n",
    "            cur=0\n",
    "            speed=f \n",
    "            roud=1\n",
    "            while speed < f+changeTime:\n",
    "                cur=cur+speed\n",
    "                best[roud]=min(best[roud],cur)\n",
    "                maxdiff=max(maxdiff,roud)\n",
    "                roud+=1\n",
    "                speed=speed*r \n",
    "        dp=[float(\"inf\")]*(numLaps+1)\n",
    "        dp[0]=0\n",
    "       # print(best)\n",
    "       # print(maxdiff)\n",
    "        for i in range(1,numLaps+1):\n",
    "            for j in range(i-1,-1,-1):\n",
    "             \n",
    "                tmp=i-j \n",
    "                if tmp <=maxdiff:\n",
    "                    dp[i]=min(dp[i],dp[j]+best[tmp]+changeTime)\n",
    "                else:\n",
    "                    break\n",
    "      \n",
    "        return dp[-1]-changeTime\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        return 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        # 轮胎 changeTime 加上跑完这一圈需要多少时间\n",
    "        # 单个轮胎使用的圈数不可能超过18 这是因为按照数据范围达到18圈以后就不如直接换轮胎\n",
    "        mi_sec = [inf for _ in range(18)] # 这个数组是单个跑i圈需要的最少时间\n",
    "        for f, r in tires:\n",
    "            index, time, sm = 1, f, 0 \n",
    "            while time <= changeTime + f:\n",
    "                sm += time\n",
    "                mi_sec[index] = sm if sm < mi_sec[index] else mi_sec[index]\n",
    "                time *= r\n",
    "                index += 1\n",
    "        f = [0] * (numLaps + 1)\n",
    "        for i in range(1, numLaps + 1):\n",
    "            f[i] = changeTime + min(f[i - j] + mi_sec[j] for j in range(1, min(18, i + 1)))\n",
    "        return f[-1] - changeTime        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        cost = [inf] * 18\n",
    "        for f, r in tires:\n",
    "            i, s, t = 1, 0, f\n",
    "            while t <= changeTime + f:\n",
    "                s += t\n",
    "                cost[i] = min(cost[i], s)\n",
    "                t *= r\n",
    "                i += 1\n",
    "        f = [inf] * (numLaps + 1)\n",
    "        f[0] = -changeTime\n",
    "        for i in range(1, numLaps + 1):\n",
    "            for j in range(1, min(18, i + 1)):\n",
    "                f[i] = min(f[i], f[i - j] + cost[j])\n",
    "            f[i] += changeTime\n",
    "        return f[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        maxTime = float(\"inf\")\n",
    "        # 预处理\n",
    "        # 最多跑，比较不同轮胎连着跑的最短时间\n",
    "        n = len(tires)\n",
    "        timeTires = [[maxTime] * n] * 18\n",
    "        bestTires = [maxTime] * 18\n",
    "        # 计算\n",
    "        for i in range(n):\n",
    "            timeTires[1][i] = tires[i][0]\n",
    "            bestTires[1] = min(bestTires[1], timeTires[1][i])\n",
    "\n",
    "        for i in range(2, 18):\n",
    "            for j in range(n):\n",
    "                timeTires[i][j] = timeTires[i - 1][j] + tires[j][0] * (tires[j][1] ** (i - 1))\n",
    "                bestTires[i] = min(bestTires[i], timeTires[i][j])\n",
    "        \n",
    "        # dp 开跑\n",
    "        dp = [float(\"inf\")] * (numLaps + 1)\n",
    "        dp[1] = bestTires[1]\n",
    "        pos = 2\n",
    "        while pos <= numLaps:\n",
    "            curLaps = 17\n",
    "            if pos <= 17:\n",
    "                dp[pos] = bestTires[pos]\n",
    "                curLaps = pos - 1\n",
    "            else:\n",
    "                dp[pos] = dp[pos - 17] + changeTime + bestTires[17]\n",
    "                curLaps -= 1\n",
    "            while curLaps > 0:\n",
    "                dp[pos] = min(dp[pos - curLaps] + changeTime + bestTires[curLaps], dp[pos])\n",
    "                curLaps -= 1\n",
    "            pos += 1\n",
    "\n",
    "        return dp[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        best=[float(\"inf\")]*18\n",
    "        maxdif=0\n",
    "        for f,r in tires:\n",
    "            one=cur=f\n",
    "            i=1\n",
    "            while one<changeTime+f:\n",
    "                one=one*r\n",
    "                best[i]=min(best[i],cur)\n",
    "                cur=cur+one\n",
    "                maxdif=max(i,maxdif)\n",
    "                i=i+1\n",
    "        dp=[0]+[float(\"inf\")]*(numLaps)\n",
    "\n",
    "        for i in range(1,numLaps+1):\n",
    "            \n",
    "            j=i-1\n",
    "            while j>=0 and (i-j)<=maxdif:\n",
    "                dp[i]=min(dp[i],dp[j]+best[i-j]+changeTime)\n",
    "                j=j-1\n",
    "        #print(dp)\n",
    "        return dp[-1]-changeTime\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        # best[i]是使用任意的单独一种轮胎，连续跑i圈所需的时间\n",
    "        best = [float('inf')] * 18\n",
    "        maxLaps = 0\n",
    "        for first, rate in tires:\n",
    "            # lap是单圈用时，total是累计用时\n",
    "            lap = total = first\n",
    "            i = 1\n",
    "            while lap < changeTime + first:\n",
    "                best[i] = min(best[i], total)\n",
    "                lap *= rate\n",
    "                total += lap\n",
    "                maxLaps = max(maxLaps, i)\n",
    "                i += 1\n",
    "        dp = [0] + [float('inf')] * numLaps\n",
    "        for i in range(1, numLaps + 1):\n",
    "            j = i - 1\n",
    "            while j >= 0 and i - j <= maxLaps:\n",
    "                # 核心代码，之前都是为它做的准备\n",
    "                # 这里虽然j是递减的，i是递增的，所以比较小的dp如dp[j]，要用之前已经被算出来了\n",
    "                dp[i] = min(dp[i], dp[j] + best[i - j] + changeTime)\n",
    "                j -= 1\n",
    "        return dp[numLaps] - changeTime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        # best[i]是使用任意的单独一种轮胎，连续跑i圈所需的时间\n",
    "        best = [float(\"inf\")] * 18\n",
    "        maxLaps = 0\n",
    "        for (f, r) in tires:\n",
    "            lap = cur = f\n",
    "            i = 1\n",
    "            while lap < changeTime + f:\n",
    "                best[i] = min(best[i], cur)\n",
    "                lap *= r\n",
    "                cur += lap\n",
    "                maxLaps = max(maxLaps, i)\n",
    "                i += 1\n",
    "        \n",
    "        f = [0] + [float(\"inf\")] * numLaps\n",
    "        for i in range(1, numLaps + 1):\n",
    "            j = i - 1\n",
    "            while j >= 0 and i - j <= maxLaps:\n",
    "                # 核心代码，之前都是为它做的准备\n",
    "                f[i] = min(f[i], f[j] + best[i - j] + changeTime)\n",
    "                j -= 1\n",
    "        \n",
    "        return f[numLaps] - changeTime\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        rem=[float(\"inf\")]*18\n",
    "        for a,b in tires:\n",
    "            tp=0\n",
    "            for i in range(18):\n",
    "                tp+=pow(b,i)*a\n",
    "                if tp<rem[i]:\n",
    "                    rem[i]=tp\n",
    "        #print(rem)\n",
    "        dp=[[float(\"inf\") for _ in range(numLaps+1)]for _ in range(18)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(18):\n",
    "            if i!=0:\n",
    "                dp[i]=dp[i-1]\n",
    "            for j in range(i+1,numLaps+1):\n",
    "                dp[i][j]=min(dp[i][j],dp[i][j-i-1]+rem[i]+changeTime)\n",
    "        #print(dp)\n",
    "        return dp[-1][-1]-changeTime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        tires.sort()\n",
    "        s = []\n",
    "        for a, b in tires:\n",
    "            while s:\n",
    "                la, lb = s[-1]\n",
    "                if a == la:\n",
    "                    if b >= lb:\n",
    "                        break\n",
    "                    else:\n",
    "                        s.pop()\n",
    "                else:\n",
    "                    if b >= lb:\n",
    "                        break\n",
    "                    else:\n",
    "                        s.append([a, b])\n",
    "            if not s:\n",
    "                s.append([a, b])\n",
    "\n",
    "        n = len(s)\n",
    "        mi = min([a for a, b in s]) + changeTime\n",
    "        rec = [inf] * (numLaps + 1)\n",
    "        rec[1] = mi\n",
    "        for a, b in s:\n",
    "            tmp = a + changeTime\n",
    "            for i in range(2, numLaps + 1):\n",
    "                now = a * b ** (i - 1)\n",
    "                if now >= mi:\n",
    "                    break\n",
    "                else:\n",
    "                    tmp += now\n",
    "                    rec[i] = min(rec[i], tmp)\n",
    "        res = [0]\n",
    "        for i in rec[1:]:\n",
    "            if i != inf:\n",
    "                res.append(i)\n",
    "            else:\n",
    "                break\n",
    "        m = len(res) - 1\n",
    "        dp = [inf] * (numLaps + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = mi\n",
    "        for i in range(2, numLaps + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                if i - j < 0:\n",
    "                    break\n",
    "                dp[i] = min(dp[i], dp[i - j] + res[j])\n",
    "        return dp[-1] - changeTime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        mintime=[0]*18\n",
    "        for i in range (1,18):\n",
    "            mintime[i]=min([f*(pow(r,i)-1)//(r-1) for f,r in tires])\n",
    "\n",
    "        dp=[inf]*(1+numLaps)\n",
    "        dp[0]=0\n",
    "        dp[1]=mintime[1]\n",
    "        for i in range (1,1+numLaps):\n",
    "            if i==1:\n",
    "                dp[i]=mintime[1]\n",
    "            else:\n",
    "                if i<=17:\n",
    "                    dp[i]=min(dp[i],mintime[i])\n",
    "                for j in range (1,1+min(17,i-1)):\n",
    "                    dp[i]=min(dp[i],mintime[j]+changeTime +dp[i-j])\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# https://leetcode.cn/problems/minimum-time-to-finish-the-race/description/\n",
    "# 完成比赛的最少时间 线性dp但是需要一点点转换\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        min_sec = [0x3f3f3f3f for _ in range(18)]\n",
    "        # 轮胎跑圈时间成指数增长\n",
    "        for f, r in tires:\n",
    "            index, s, time = 1, 0, f\n",
    "            while time <= f + changeTime:\n",
    "                s += time\n",
    "                min_sec[index] = min(s, min_sec[index])\n",
    "                time *= r\n",
    "                index += 1\n",
    "        dp = [0 for _ in range(numLaps + 1)]\n",
    "        for i in range(1, numLaps + 1):\n",
    "            dp[i] = min(dp[i - j] + min_sec[j] + changeTime for j in range(min(i + 1, 18)))\n",
    "        return dp[-1] - changeTime\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        best=[float(\"inf\")]*18\n",
    "        maxdif=0\n",
    "\n",
    "        for f,r in tires:\n",
    "            one,cur=f,f\n",
    "            i=1\n",
    "            while one<changeTime+f:\n",
    "                one=one*r\n",
    "                best[i]=min(best[i],cur) \n",
    "                cur=cur+one\n",
    "                maxdif=max(i,maxdif)\n",
    "                i=i+1\n",
    "        dp=[float(\"inf\")]*(numLaps)\n",
    "        dp=[0]+dp\n",
    "\n",
    "        for i in range(1,numLaps+1):\n",
    "            j=i-1\n",
    "            while j>=0 and i-j<=maxdif:\n",
    "                dp[i]=min(dp[i],dp[j]+best[i-j]+changeTime)\n",
    "                j=j-1\n",
    "        return dp[-1]-changeTime                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\r\n",
    "        min_sec = [inf] * 18\r\n",
    "        for f, r in tires:\r\n",
    "            x, time, sum = 1, f, 0\r\n",
    "            while time <= changeTime + f:\r\n",
    "                sum += time\r\n",
    "                min_sec[x] = min(min_sec[x], sum)\r\n",
    "                time *= r\r\n",
    "                x += 1\r\n",
    "\r\n",
    "        f = [0] * (numLaps + 1)\r\n",
    "        f[0] = -changeTime\r\n",
    "        for i in range(1, numLaps + 1):\r\n",
    "            f[i] = changeTime + min(f[i - j] + min_sec[j] for j in range(1, min(18, i + 1)))\r\n",
    "        return f[numLaps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        best = [float('inf')] * 18\n",
    "        maxLaps = 0\n",
    "        for first, rate in tires:\n",
    "            lap = total = first\n",
    "            i = 1\n",
    "            while lap < changeTime + first:\n",
    "                best[i] = min(best[i], total)\n",
    "                lap *= rate\n",
    "                total += lap\n",
    "                maxLaps = max(maxLaps, i)\n",
    "                i += 1\n",
    "        dp = [0] + [float('inf')] * numLaps\n",
    "        for i in range(1, numLaps + 1):\n",
    "            j = i - 1\n",
    "            while j >= 0 and i - j <= maxLaps:\n",
    "                dp[i] = min(dp[i], dp[j] + changeTime + best[i - j])\n",
    "                j -= 1\n",
    "        return dp[numLaps] - changeTime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        # best[i]是使用任意的单独一种轮胎，连续跑i圈所需的时间\n",
    "        best = [float('inf')] * 18\n",
    "        maxLaps = 0\n",
    "        for first, rate in tires:\n",
    "            # lap是单圈用时，total是累计用时\n",
    "            lap = total = first\n",
    "            i = 1\n",
    "            while lap < changeTime + first:\n",
    "                best[i] = min(best[i], total)\n",
    "                lap *= rate\n",
    "                total += lap\n",
    "                maxLaps = max(maxLaps, i)\n",
    "                i += 1\n",
    "        dp = [0] + [float('inf')] * numLaps\n",
    "        for i in range(1, numLaps + 1):\n",
    "            j = i - 1\n",
    "            while j >= 0 and i - j <= maxLaps:\n",
    "                # 核心代码，之前都是为它做的准备\n",
    "                dp[i] = min(dp[i], dp[j] + best[i - j] + changeTime)\n",
    "                j -= 1\n",
    "        return dp[numLaps] - changeTime\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        best = [float('inf')] * 18\n",
    "        maxLaps = 0\n",
    "        for first, rate in tires:\n",
    "            lap = total = first\n",
    "            i = 1\n",
    "            while lap < changeTime + first:\n",
    "                best[i] = min(best[i], total)\n",
    "                lap *= rate\n",
    "                total += lap\n",
    "                maxLaps = max(maxLaps, i)\n",
    "                i += 1\n",
    "        dp = [0] + [float('inf')] * numLaps\n",
    "        for i in range(1, numLaps + 1):\n",
    "            j = i - 1\n",
    "            while j >= 0 and i - j <= maxLaps:\n",
    "                dp[i] = min(dp[i], dp[j] + best[i - j] + changeTime)\n",
    "                j -= 1\n",
    "        return dp[numLaps] - changeTime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        T = changeTime.bit_length()\n",
    "        best_for_t = [0] + [inf] * T\n",
    "\n",
    "        def unique_and_smaller_tires():\n",
    "            lo_r = inf\n",
    "            for f, r in sorted({(f, r) for f, r in tires}):\n",
    "                if r >= lo_r: continue\n",
    "                lo_r = r\n",
    "                yield (f, r)\n",
    "\n",
    "        for f, r in unique_and_smaller_tires():\n",
    "            t, s, tot = 1, f, 0\n",
    "            while s < changeTime + f:\n",
    "                tot += s\n",
    "                best_for_t[t] = min(best_for_t[t], tot)\n",
    "                s *= r\n",
    "                t += 1\n",
    "\n",
    "        dp = [-changeTime]\n",
    "        for x in range(1, numLaps + 1): dp.append(changeTime + min(dp[x - t] + best_for_t[t] for t in range(1, 1 + min(T, x))))\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from cmath import inf\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# https://leetcode.cn/problems/minimum-time-to-finish-the-race/description/\n",
    "# 完成比赛的最少时间 线性dp但是需要一点点转换\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        min_sec = [inf for _ in range(18)]\n",
    "        # 轮胎跑圈时间成指数增长\n",
    "        for f, r in tires:\n",
    "            index, s, time = 1, 0, f\n",
    "            while time <= f + changeTime:\n",
    "                s += time\n",
    "                min_sec[index] = min(s, min_sec[index])\n",
    "                time *= r\n",
    "                index += 1\n",
    "        dp = [0 for _ in range(numLaps + 1)]\n",
    "        for i in range(1, numLaps + 1):\n",
    "            dp[i] = min(dp[i - j] + min_sec[j] + changeTime for j in range(min(i + 1, 18)))\n",
    "        return dp[-1] - changeTime\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        mink = [0] \n",
    "        tires.sort(key = lambda x: x[0])\n",
    "        minf = tires[0][0]\n",
    "        # mink.append(minf)\n",
    "        tempr = tires[0][1]\n",
    "        tempf = tires[0][0]\n",
    "        t = 0\n",
    "        tires = [(0, x[0], x[1]) for x in tires]\n",
    "        k = 0\n",
    "        while k < numLaps:\n",
    "            heap = [(t + tempf, tempf * tempr, tempr)]\n",
    "            for l, f, r in tires:\n",
    "                if r < tempr:\n",
    "                    heapq.heappush(heap, (l + f, f * r, r))\n",
    "            t, tempf, tempr = heapq.heappop(heap)\n",
    "            if t > k * changeTime + (k + 1) * minf:\n",
    "                break\n",
    "            mink.append(t)\n",
    "            tires = heap\n",
    "            k += 1\n",
    "        # print(mink)\n",
    "        dp = [0] * (numLaps + 1)\n",
    "        dp[0] = -changeTime\n",
    "        for i in range(1, numLaps + 1):\n",
    "            dp[i] = dp[i-1] + changeTime + mink[1]\n",
    "            for j in range(1, min(k, i) + 1):\n",
    "                dp[i] = min(dp[i], dp[i-j] + changeTime + mink[j])\n",
    "        # print(dp)\n",
    "        return dp[numLaps]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        tires.sort()\n",
    "        new_tires = []\n",
    "        Max_len = 0\n",
    "        for t in tires:\n",
    "            if new_tires == [] or t[1] < new_tires[-1][1]:\n",
    "                change_len = math.ceil(math.log(changeTime/t[0] + 1) / math.log(t[1])) + 1\n",
    "                Max_len = max(Max_len, change_len)\n",
    "                t.append(change_len)\n",
    "                new_tires.append(t)\n",
    "        print(new_tires)\n",
    "        print(Max_len)\n",
    "\n",
    "        min_time = [0] * Max_len\n",
    "        for t in new_tires:\n",
    "            time = [0] * Max_len\n",
    "            st = t[0]\n",
    "            for c in range(1, Max_len):\n",
    "                time[c] = st + time[c-1]\n",
    "                min_time[c] = min(min_time[c], time[c]) if min_time[c] > 0 else time[c]\n",
    "                st *= t[1]\n",
    "        print(min_time)\n",
    "\n",
    "        dp = [0] * (numLaps+1)\n",
    "        dp[1] = min_time[1]\n",
    "        for i in range(2, numLaps+1):\n",
    "            dp[i] = min(dp[i-j] + min_time[j] + (0 if j==i else changeTime) for j in range(1, min(i+1, Max_len)))\n",
    "        print(dp)\n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, n: int) -> int:\n",
    "        L = []\n",
    "        G = defaultdict(list)\n",
    "        for f,r in tires:\n",
    "            G[r].append(f)\n",
    "        for a,b in G.items():\n",
    "            L.append([min(b),a])\n",
    "        L.sort(key = lambda x:x[1])\n",
    "        if len(L) > 1:\n",
    "            pos = 1\n",
    "            while pos < len(L):\n",
    "                while pos < len(L) and L[pos][0] >= L[pos-1][0]:\n",
    "                    L.pop(pos)\n",
    "                pos += 1\n",
    "        \n",
    "            \n",
    "        F = [0] * (n+1)\n",
    "        \n",
    "        pos = len(L)-1\n",
    "        f1,r1 = L[pos]\n",
    "        # print(L)\n",
    "        for i in range(1,n+1):\n",
    "            F[i] = min([f*(r**i-1)//(r-1) for f,r in L])\n",
    "        # print(F)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(lft):\n",
    "            if lft == 0:return 0\n",
    "            res = F[lft]\n",
    "            for i in range(1,lft):\n",
    "                res = min(res,dfs(i) + F[lft-i] + changeTime)\n",
    "            return res\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        t = [inf] * 18\n",
    "        for f, r in tires:\n",
    "            total, res = f, 1\n",
    "            for j in range(18):\n",
    "                t[j] = min(t[j], total)\n",
    "                res *= r\n",
    "                total += f * res\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(re):\n",
    "            if not re:\n",
    "                return 0\n",
    "\n",
    "            return min(changeTime + t[i - 1] + dfs(re - i) for i in range(1, min(18, re + 1)))\n",
    "\n",
    "        ans = dfs(numLaps) - changeTime\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        # 2 <= ri <= 10^5    从数据范围来看一条tile不可能用超过16圈，所以只需要计算1圈换胎-16圈换胎的最优解就行了\n",
    "        cost = [inf] * 17\n",
    "        for n in range(1, 17):\n",
    "            for f, r in tires:\n",
    "                v = (r**n-1) / (r-1)\n",
    "                v = int(v*f)\n",
    "                cost[n] = min(cost[n], v)\n",
    "        \n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for k in range(1, 1+min(16, i)):\n",
    "                ans = min(ans, changeTime + cost[k] + f(i-k))\n",
    "            return ans\n",
    "        \n",
    "        return f(numLaps) - changeTime\n",
    "            \n",
    "                \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:\n",
    "        level = []\n",
    "        _min = float('inf')\n",
    "        for f, r in tires:\n",
    "            level.append([f, f, f, r])\n",
    "            _min = min(_min, f)\n",
    "        minT = [0]*(numLaps+1)\n",
    "        for l in range(1, numLaps+1):\n",
    "            half = l >> 1\n",
    "            lMin = _min\n",
    "            for h in range(1, half+1):\n",
    "                lMin = min(lMin, minT[l-h] + changeTime + minT[h])\n",
    "            minT[l] = lMin\n",
    "            if l < numLaps and level:\n",
    "                j, _min = 0, float('inf')\n",
    "                for accu, e, f, r in level:\n",
    "                    e *= r\n",
    "                    if e >= changeTime + f:\n",
    "                        continue\n",
    "                    accu += e\n",
    "                    entryJ = level[j]\n",
    "                    entryJ[0] = accu\n",
    "                    entryJ[1] = e\n",
    "                    entryJ[2] = f\n",
    "                    entryJ[3] = r\n",
    "                    _min = min(_min, accu)\n",
    "                    j += 1\n",
    "                if j:\n",
    "                    del level[j:]\n",
    "                else:\n",
    "                    level = None\n",
    "        return minT[-1] \n",
    "        # f*(r**x-1)//(r-1)\n",
    "        # T[r] = min(T[k] + c + T[r-k], M[r])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
